package jianzhiOffer;

import java.util.LinkedList;
import java.util.List;

//剑指 Offer 34. 二叉树中和为某一值的路径
public class Num34_pathSum {
    LinkedList<List<Integer>> res = new LinkedList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        //将待选结果集放到结果集里面
        recur(root,target);
        return res;
    }
    private void recur(TreeNode root, int target) {
        if (root == null){
            return;
        }
        //放入待选结果集中
        path.add(root.val);
        target -= root.val;
        if (target == 0 && root.left == null && root.right == null){
            res.add(new LinkedList<>(path));
        }
        recur(root.left,target);
        recur(root.right,target);
        //回溯
        path.removeLast();
    }


}
